/*
 * TreeOperation.java
 * 
 * Created on Aug 22, 2007, 12:47:13 PM
 * 
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package galronnlp.util;

/**
 *
 * @author cbrew
 */
public class TreeOperation {
    /*
     * A small set of elementary edit operations
     * for transforming trees.  
     * 
     * The tree operations use an auxilliary
     * structure that augments the tree with
     * a cursor marking the editor's current
     * location. Destructive editing operations
     * change the tree at the current cursor
     * position. Non-destructive edit operations
     * move the cursor but do not alter the structure
     * of the tree. These operations maintain the invariant
     * that every node has a parent.
  
     * To ensure this, there is a dummy
     * node providing a single root at the top of the tree hierarchy. 
     * If desired, the edit operations can be used to  equip the root node with 
     * multiple children, so the editor will actually be capable of generating 
     * forests (it may be helpful to restrict the root to a single
     * daughter if this generality gets confusing)
     * 
     * The destructive edit operations are:
     *  - addNode() add a new empty node to the left of  the cursor, 
     *    This new node is initially childless and has the
     *    empty string as its label.
     * 
     *    If we apply addNode()
     *                    M
     *      D[0] ... D[k] | D[k+1] ... D[n-1]
     * 
     *     becomes 
     *                      M
     *      D[0] ... D[k] ND | D[k+1] ... D[n-1]
     * 
     *  where ND is a newly created daughter.
     * 
     *  - addNode(Node n) the same as above, but insert the specified
     *    node rather than creating a new one.
     * 
     *  - deleteNode() delete a node to the left of the cursor,
     *    This is the inverse of addNode. It can also be used to
     *    delete nodes that have daughters and non-trivial labels.
     *    This operation therefore returns the deleted node, so 
     *    that no information need be lost. Raises an exception 
     *    if there is no node to the left of the cursor.
     *   
     *  - relabelNode() change the label of the node to the left
     *    of the cursor. Takes the new label as argument.
     *    Returns the old label. Raises an exception
     *    if there is no node to the left of the cursor.
     *    This is its own inverse.
     * 
     * The non-destructive operations move the cursor. In these
     *  descriptions we use the term "currentNode" to refer to
     *  the node immediately to the left of the current cursor
     *  position.
     *    
     *  - moveDown places the cursor just before the first
     *    child of the current node. If the current node is 
     *    childless, a new empty list of daughters will be 
     *    created, and the cursor placed at the leftmost edge
     *    of that list. If there is no current node (which can
     *    happen if we are at the left edge of a list of daughters)
     *    an exception will be raised. 
     *  - moveUp places the cursor to the right of the parent
     *    of the current node. An exception is raised if an attempt is 
     *    made to place the cursor to the left of the dummy root node.
     *  - moveRight moves the cursor one position to the right.
     *    An exception is raised if the cursor is already at the
     *    extreme right of a list of siblings.
     *  - moveLeft moves the cursor one position to the left. 
     *    An exception is raised if the cursor is already at the
     *    extreme left of a list of siblings.
     * 
     * Every tree can be associated with a unique sequence of operations that creates
     * it. This is the trace of a left-corner derivation. This sequence involves an
     * addNode for each node of the tree, along with one upward and one downward 
     * traversal for each node in the tree.
     * 
     * Given this representation, tree editing can be implemented by instead editing 
     * left corner derivations. For example, removing unary branches is implemented
     * by replacing the sequence
     *   down - label - down - TREES - up - up
     *  with
     *     down-TREES-up
     *  where TREES represents a balanced sequence starting with down and ending
     *  with up
     * /
    public TreeOperation() {
    }

}
